Rendering an image on a raster display requires the formation of the raster image at some point in the printing process. In the case of characters, a raster bit map of each needed character can be stored in memory and then simply copied from memory to a printer input buffer whenever that character is required. A complete set of characters can be maintained in memory, but this requires storing each particular character in every needed point size and resolution, which can use up large quantities of memory. Alternatively, a set of characters can be encoded in some way, then converted into a bit map for a particular size character at a particular resolution appropriate for a selected display device. Characters which will be reused can be stored in cache memory to facilitate faster printing. A typical printing job requires a full set of lower case characters and many but not all capital letters at a single size and resolution. Thus bit maps of each of these characters can be generated and held in cache memory for the duration of the job, after which the cache memory can be flushed and filled with characters needed for the next job. Typical printer memory can accommodate a small number of fonts, enough for a simple job. When a job calls for a large number of fonts and/or point sizes, the capacity of cache memory may be exceeded, requiring some character bit maps to be generated multiple times.
In a preferred embodiment, the device is used to convert PostScript.RTM. Type 1 font outlines to bit maps. PostScript was developed by Adobe Systems Inc. (hereinafter "Adobe"), the assignee of the subject invention. The PostScript system was developed to communicate high-level graphic information to digital laser printers. It is a flexible, compact and powerful language for rendering characters from stored outline fonts, for expressing graphic regions and for performing general programming tasks. The preferred embodiment of the device of this invention is described in the context of a PostScript printer, typesetter or image-setter.
The PostScript language, use and applications are thoroughly described in a number of books published by Adobe, including POSTSCRIPT LANGUAGE REFERENCE MANUAL (Second Edition, 1990) and POSTSCRIPT LANGUAGE PROGRAM DESIGN (1988), each of which is incorporated herein by reference. PostScript and related page description languages are useful with typesetters, image-setters, color printers and high throughput printers as well as high-resolution video or other display devices.
The present invention is useful in many currently available printing environments. Outline fonts are used in conjunction with many typesetting and printing combinations, using Apple.RTM. Macintosh.RTM., IBM.RTM. PC, Sun.RTM. and other UNIX-based computers with one or more of several marking (printing) or display devices. Current software includes Adobe's PostScript and ATM.TM. software and hardware, and outline font programs from Bitstream and Compugraphic. Page description languages used to control printers include Adobe's PostScript language, Hewlett Packard's PCL, Canon's LIPS, NEC's NPDL and other languages by Kyocera and Xerox.
Printers, video display and other such devices are sometimes called marking devices or marking engines. A raster image processor (RIP) associated with a marking engine converts input information and commands into a rasterized (bit-mapped) region suitable for display on the associated output device. Commercially available devices include the Apple LaserWriter.RTM., the Linotronic.RTM. 100 and 300, the Adobe Atlas RIP, the Emerald RIP and Hewlett-Packard DeskWriter.TM. and LaserJet.TM.. A marking engine generally prints characters from stored bit maps by simply transferring the pattern of bits from memory to the output device. This requires a bit map of the character in the correct size and resolution.
The main advantage of outline fonts over bit mapped fonts is also the main disadvantage. An outline font can be used to generate a bit map for a character of any size from a single outline font. This provides flexibility and compact storage, but costs time in preparing each required bit map and incurs the added burden of ensuring that all bit map renditions have aesthetic appeal. A bit mapped font can be specifically edited to produce optimal results, but only for a specific size. Additional sizes require additional bit maps. Bit mapped fonts have traditionally enjoyed a speed advantage as well in that the bit map can be printed directly. The trade-off is speed vs. storage capacity requirements.
Essentially all programs using outline fonts must convert outline information into a bit map before printing a character on a raster printer. In a typical application, outlines are defined in a high resolution coordinate system, generally called character space. In order to print on a marking engine, the outline must be scaled to the required size and mapped to a coordinate system appropriate for the marking engine. The second coordinate space is generally called device space. The outline in device space is filled with a series of pixels to approximate the original outline. Characters may be adjusted or "hinted" in either character space or device space to improve alignment of the final character on the device space pixel grid.
Previous methods of converting character outlines to scaled character bit maps were software based, which allowed flexibility but significantly limited the speed at which character bit maps could be generated. The limitations of software based renderers become particularly acute for printing jobs which require a large number of different fonts or sizes, since each character at each size in each font must be available to the marking engine as a bit map. If a required character is not available in the required size and font, then the corresponding outline must be adjusted and converted. The limitations of software-based renderers are also significant in printing foreign languages such as Japanese which use a large number of characters with only limited repetition. Each time a character bit map is not available in cache memory, a new bit map must be generated. The bit map is usually stored, displacing a previously stored character bit map if the available memory is full.
The problem of scaling outlines to produce bit maps has been a challenge for many years. Many of the problems of analyzing outlines to produce bit maps at an arbitrary scale have been solved in the Adobe ATM product. The methods used in ATM are described in U.S. patent application Ser. Nos. 388,336 and 388,339 by Paxton et al. and Nos. 539,222 and 552,788 by Byron et al., all assigned to Adobe and all incorporated herein by reference. Some of the methods described therein, such as analyzing outlines, identifying crosses and tracing paths have been improved and form the basis for the present invention.